<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>

<body>
  <script>
    /* 栈的封装 */
    function Stack() {
      this.elements = []
    }
    Stack.prototype.push = function(element) { // 向栈里添加元素
      this.elements.push(element)
    }
    Stack.prototype.pop = function() { // 弹出栈顶元素
      return this.elements.pop()
    }
    Stack.prototype.peek = function() { //返回栈顶元素,单步操作栈
      return this.elements[this.elements.length - 1]
    }
    Stack.prototype.isEmpty = function() { //判断栈是否为空
      return this.elements.length === 0
    }
    Stack.prototype.size = function() { //返回栈的大小
      return this.elements.length
    }
    Stack.prototype.clear = function() { //清空栈
      this.elements = []
    }
    Stack.prototype.toString = function() {
      var str = ''
      for (var i = 0, el = this.elements[i++]; i < this.elements.length;) {
        str += el
      }
      return str
    }

    /* 利用将十进制转成二进制 */
    function dec2bin(dec) {
      var stack = new Stack()
      while (dec > 0) {
        stack.push(dec % 2) //将余数放进栈中, 因为二进制是依靠余数决定的
        dec = Math.floor(dec / 2) // 考虑到余数的情况, 余数的情况时向下取整
      }
      var binary = ''
      while (!stack.isEmpty()) {
        binary += stack.pop()
      }
      return console.log(binary)
    }

    // dec2bin(100) //测试用例:1100100
    // dec2bin(10) //测试用例:1010

    /*-------------------------------------------------------------------------------*/

    function Queue() {
      this.items = []
    }
    Queue.prototype.enqueue = function(element) {
      this.items.push(element)
    }
    Queue.prototype.dequeue = function() {
      return this.items.shift()
    }
    Queue.prototype.front = function() {
      return this.items[0]
    }

    Queue.prototype.isEmpty = function() {
      return this.items.length === 0
    }
    Queue.prototype.size = function() {
      return this.items.length
    }
    /* 击鼓传花游戏函数 */
    function passGame(nameList, num) {
      var queue = new Queue() //创建一个队列

      for (var i = 0, el; el = nameList[i++];) { //将所有玩家加入队列
        queue.enqueue(el)
      }
      // 开始游戏
      while (queue.size() > 1) { //当队列中大于一位选手时, 游戏继续
        // 核心思路, 数到num的玩家重新放在队列后, 此时num玩家在队首, 出队列.重新计数
        for (var i = 0; i < num - 1; i++) { //第num个选手, 下标为num-1
          queue.enqueue(queue.dequeue()) //队首元素先出队列, 在加入队列, 重新排队
        }
        queue.dequeue() // 真正需要移除队列的玩家
      }
      return console.log(queue.front())
    }
    var gameList = ['马超', '赵云', '黄忠', '张飞']
    //passGame(gameList,3)  //测试用例

    /*-------------------------------------------------------------------------------*/
    /* 优先级队列实现 */
    function PriorityQueue() {
      Queue.apply(this, ...arguments)
    }
    PriorityQueue.prototype = Object.create(Queue.prototype) //继承队列类的方法
    PriorityQueue.prototype.constructor = PriorityQueue // 修改优先级队列的constructor

    PriorityQueue.prototype.enqueue = function(element, priority) {
      function QueueElement(element, priority) { //内部类, 用来保存元素和优先级的
        this.element = element
        this.priority = priority
      }
      var el = new QueueElement(element, priority)
      if (this.items.length === 0) { //如果当前队列中没有元素,直接添加
        this.items.push(el)
      } else {
        var added = false
        for (var i = 0, ele; ele = this.items[i++];) {
          if (el.priority < ele.priority) { //如果元素的优先级高于当前元素的优先级,就插入该元素
            this.items.splice(i - 1, 0, el) //因为i已经++过, 所以当前元素的下标是i-1
            added = true //标记添加过
            break //添加完以后终止循环
          }
        }
        if (!added) { //如果优先级最低, 到循环结束也没加入, 则添加到队列尾部
          this.items.push(el)
        }
      }
    }

    //测试用例
    // var pri = new PriorityQueue() 
    // pri.enqueue('主管',100)
    // pri.enqueue('总裁',1)
    // pri.enqueue('校长',10)
    // pri.enqueue('副校长',20)
    // console.log(pri)

    /*-------------------------------------------------------------------------*/

    function LinkedList() {
      /* 内部类用于封装节点信息 */
      function Node(element) {
        this.element = element
        this.next = null //单链表的指针
      }
      this.head = null //头指针
      this.length = 0 // 记录链表的长度

      /* 尾部添加节点 */
      LinkedList.prototype.append = function(element) {
        var node = new Node(element)
        if (this.length === 0) { //链表节点为0时候,让head指向首节点
          this.head = node
        } else { // 有节点时, 找到最后一个节点,指向该节点
          var currentNode = this.head //定义一个容器保存节点
          while (currentNode.next) { // 线性查找
            currentNode = currentNode.next // 赋值保存该节点
          }
          currentNode.next = node //此时currentNode为最后一个节点
        }
        this.length += 1 //添加成功, 长度+1
      }

      LinkedList.prototype.toString = function() {
        var str = ''
        var node = this.head
        for (var i = 0; i < this.length; i++) {
          str += node.element + ' '
          node = node.next
        }
        return str
      }

      LinkedList.prototype.insert = function(position, element) {
        if (position > this.length || position < 0) return false //如果下标越界, 插入失败返回false

        if (position === this.length) return this.append(element) //如果插入末尾, 调用append方法

        var node = new Node(element)

        if (position === 0) { //插入头部, 修改head指针
          node.next = this.head //将当前指针指向第一个元素
          this.head = node //将head指针指向插入的node
        } else { // 插入中间, 查找positon位置的算法
          var previousNode = null // 前节点的初始值为null
          var currentNode = this.head //取出第一个node节点
          for (var i = 0; i < this.length; i++) {
            if (i === position) {
              previousNode.next = node
              node.next = currentNode
              break;
            }
            previousNode = currentNode
            currentNode = currentNode.next
          }
        }
        this.length += 1
      }

      LinkedList.prototype.update = function(position, element) {
        if (position > this.length - 1 || position < 0) return false
        var currentNode = this.head
        var index = 0
        while (index++ < position) { // 找到更新的元素
          currentNode = currentNode.next
        }
        currentNode.element = element //更新元素
      }

      LinkedList.prototype.get = function(position) {
        if (position > this.length - 1 || position < 0) return null
        var index = 0
        if (position === 0) {
          return this.head
        } else {
          var currentNode = this.head
          while (index++ < position) {
            currentNode = currentNode.next
          }
          return currentNode
        }

      }

      LinkedList.prototype.removeAt = function(position) {
        if (postion < 0 || position > this.length - 1) return false

        var preNode = null
        var currentNode = this.head

        if (position === 0) {
          this.head = this.head.next
        } else if (position === this.length - 1) {
          while (currentNode.next) {
            preNode = currentNode
            currentNode = currentNode.next
          }
          preNode.next = null
        } else {
          var index = 0
          while (index++ < position) {
            preNode = currentNode
            currentNode = currentNode.next
          }
          preNode.next = currentNode.next
        }
      }
      LinkedList.prototype.indexOf = function(element) {
        var index = 0
        var currentNode = this.head
        while (currentNode) {
          if (currentNode.element == element) return index
          currentNode = currentNode.next
          index += 1
        }
        return -1
      }

      LinkedList.prototype.remove = function(element) {
        var index = this.indexOf(element)
        if (index === -1) return false
        this.removeAt(index)
      }
    }

    //测试代码
    // var linkedList = new LinkedList()  
    // linkedList.append('关羽')
    // linkedList.append('张飞')
    // linkedList.append('赵云')
    // linkedList.append('诸葛亮')
    // linkedList.insert(2,'许褚')
    // console.log(linkedList.toString())

    /*-------------------------------------------------------------------------*/
    function DoublyLinkedList() {
      this.length = 0
      this.head = null
      this.tail = null

      function Node(element) {
        this.next = null
        this.prev = null
        this.element = element
      }

      DoublyLinkedList.prototype.append = function(element) {
        var node = new Node(element)

        if (this.length === 0) {
          this.head = this.tail = node //双向链表的头尾指针指向node
        } else {
          this.tail.next = node // 尾结点的下一个指针指向新添加的
          node.prev = this.tail // 新添加的节点前一个指向原来的tail节点
          this.tail = node // 保留当前尾结点
        }
        this.length += 1
      }

      DoublyLinkedList.prototype.toString = function() {
        var str = ""
        var currentNode = this.head
        while (currentNode) {
          str += currentNode.element + ' '
          currentNode = currentNode.next
        }
        return str
      }

      DoublyLinkedList.prototype.forwardTostring = function() {
        var str = ""
        var currentNode = this.tail
        while (currentNode) {
          str += currentNode.element + ' '
          currentNode = currentNode.prev
        }
        return str
      }

      DoublyLinkedList.prototype.backwardTostring = function() {
        return this.toString()
      }

      DoublyLinkedList.prototype.insert = function(position, element) {
        if (position < 0 || position > this.length) return false //边界检查

        var node = new Node(element)
        if (this.length === 0) { //尚未创建节点
          this.head = this.tail = node
        } else { //已经创建节点
          if (position === 0) { //插入头部
            node.next = this.head
            this.head = node
          } else if (position === this.length) {
            return this.append(element) //直接结束 不让length++
          } else {
            var currentNode = this.head
            var preNode = null
            var index = 0
            while (index++ < position) {
              preNode = currentNode
              currentNode = currentNode.next
            }
            node.prev = preNode
            node.next = currentNode
            preNode.next = node
            currentNode.prev = node
          }
        }
        this.length += 1
      }

      DoublyLinkedList.prototype.get = function(position) {
        if (position < 0 || position > this.length - 1) return null

        var currentNode
        var index
        if ((this.length / 2) < position) { // 从前向后找
          currentNode = this.head
          index = 0
          while (index++ < position) {
            currentNode = currentNode.next
          }
        } else { // 从后向前找
          index = this.length - 1
          currentNode = this.tail
          while (index-- > position) {
            currentNode = currentNode.prev
          }
        }
        return currentNode.element
      }

      DoublyLinkedList.prototype.update = function(position, element) {
        if (position < 0 || position > this.length - 1) return null
        var index = 0
        var currentNode = this.head
        while (currentNode) {
          if (currentNode.element === element) {
            return currentNode.element = element
          }
          currentNode = currentNode.next
        }
        return null
      }

      DoublyLinkedList.prototype.indexOf = function(element) {
        var index = 0
        var currentNode = this.head
        while (currentNode) {
          if (currentNode.element === element) {
            return index
          }
          currentNode = currentNode.next
          index += 1
        }
      }

      DoublyLinkedList.prototype.removeAt = function(position) {
        if (position < 0 || position > this.length - 1) return null

        var currentNode
        if (this.length === 1) { //只有一个节点时候
          currentNode = this.head
          this.head = this.tail = null
        } else { // 有多个节点时
          if (position === 0) { //删除头节点时候, 不用操作更头节点的next指针, 所以提前拿出来操作
            currentNode = this.head
            this.head.next.prev = null
            this.head = this.this.head.next
          } else if (position === this.length - 1) { //删除尾节点时候, 不用操作更尾节点的prev, 所以提前拿出来处理
            currentNode = this.tail
            this.tail.prev.next = null
            this.tail = this.tail.prev
          } else { // 删除中间节点的时候
            var index
            if (position < (this.length / 2)) { //从前到后查询
              index = 0
              currentNode = this.head
              while (index++ < position) {
                currentNode = currentNode.next
              }
            } else { // 从后到前查询
              index = this.length - 1
              currentNode = this.tail
              while (index-- > position) {
                currentNode = currentNode.prev
              }
            }
            currentNode.prev.next = currentNode.next
            currentNode.next.prev = currentNode.prev
          }
        }

        this.length -= 1
        return currentNode.element
      }

      DoublyLinkedList.prototype.remove = function(element) {
        var index = this.indexOf(element)
        return this.removeAt(index)
      }

      DoublyLinkedList.prototype.isEmpty = function() {
        return this.length === 0
      }

      DoublyLinkedList.prototype.size = function() {
        return this.length
      }

      DoublyLinkedList.prototype.getHead = function() {
        return this.head
      }

      DoublyLinkedList.prototype.getTail = function() {
        return this.tail
      }
    }

    // var list = new DoublyLinkedList()
    // list.append('关羽')
    // list.append('张飞')
    // list.append('赵云')
    // list.insert(1,'诸葛亮')
    // console.log(list.get(2))
    // console.log(list)

    /* ----------------------------------------------------------------- */
    function MySet() {
      this.items = {}

      // 不考虑key为对象等情况
      MySet.prototype.add = function(value) {
        if (this.items[value]) return false
        this.items[value] = value
        return true
      }

      MySet.prototype.has = function(value) {
        return Object.hasOwnProperty.call(this.items, value)
      }

      MySet.prototype.clear = function() {
        this.items = {}
        return true
      }

      MySet.prototype.size = function() {
        return Object.keys(this.items).length
      }

      MySet.prototype.values = function() { //这里是模仿Set的values方法
        function* valuesGenerator() {
          for (let key in this.items) {
            yield this.items[key]
          }
        }
        return valuesGenerator.call(this) //需要改变this
      }

      MySet.prototype.union = function(set1) {
        if (!(set1 instanceof MySet)) throw new TypeError('Parameter must be a Set')
        var set = new MySet() //新建一个集合, 保存并集
        var iterator1 = this.values() // 自己的值迭代器
        var iterator2 = set1.values() // 传入集合的值迭代器
        var value1 = iterator1.next()
        var value2 = iterator2.next() // 用来保存每次执行next返回的对象

        while (!(value1.done && value2.done)) { //只要有一个没执行完就一直迭代
          set.add(value1.value) //add方法自动去重了
          set.add(value2.value)
          value1 = iterator1.next()
          value2 = iterator2.next()
        }
        return set
      }

      MySet.prototype.difference = function(set) {
        var values = Object.values(this.items)
        var newSet = new MySet()
        for (var i = 0, value; value = values[i++];) {
          if (!set.has(el)) {
            newSet.add(el)
          }
        }
        return newSet
      }

      MySet.prototype.subset = function(set) {
        var values = Object.values(this.items)
        for (var i = 0, value; value = values[i++];) {
          if (!set.has(value)) {
            return false
          }
        }
        return true
      }

      MySet.prototype.insertsection = function(set) {
        var values = Object.values(this.items)
        var newSet = new MySet()

        for (var i = 0, value; value = values[i++];) {
          if (set.has(value)) {
            newSet.add(value)
          }
        }

        return newValue
      }
    }

    var mySet = new MySet()
    var mySet2 = new MySet()
    mySet.add(1)
    mySet.add(2)
    mySet.add(3)
    mySet2.add(1)
    mySet2.add(2)
    mySet2.add(3)
    mySet2.add(4)
    mySet2.add(5)
    // console.log(mySet)
    // console.log('是否存在1',mySet.has(1))
    // console.log('集合长度',mySet.size())
    // var iterator = mySet.values()
    // console.log(iterator.next().value)
    // console.log(iterator.next().value)
    // console.log(iterator.next().value)
    // console.log('集合求并集',mySet.union(mySet2))


    /* 哈希表 */
    function HashTable() {
      this.limit = 7 // 记录最外层数组的容量, 初始值暂时为7, 必须是个质数, 影响元素的离散度
      this.storage = [] // 最外层的数组
      this.count = 0 // 记录哈希表内元素的个数

      /* 将key字符串, 转为hashCode */
      HashTable.prototype.hashFunc = function(key) {
        // 1. 将储存的key字符串, 转为大范围数字
        var hashCode = 0
        for (var i = 0; i < key.length; i++) { //秦九韶算法
          hashCode = 37 * hashCode + key.charCodeAt(i) //为什么取37, 不知道...
        }

        // 2. 通过取余算法返回下标
        return hashCode % this.limit
      }

      /* 向哈希表内添加, 或者修改元素 */
      HashTable.prototype.put = function(key, value) {
        // 1. 将key转为下标, 查找到该下标
        var index = this.hashFunc(key)
        // 2.如果下标内还未创建存储桶, 则创建一个
        var bucket = this.storage[index]
        if (!bucket) {
          bucket = []
          this.storage[index] = bucket
        }
        // 3. 桶内查询元素, 查询到则修改元素值
        for (var i = 0, el; el = bucket[i++];) {
          if (el[0] === key) { // 桶内依然用数组存储key,value
            el[1] = value
            return
          }
        }
        // 4.未线性查询到, 直接添加到桶最后
        bucket.push([key, value])
        this.count += 1 //元素个数加1

        // 5.添加后判断容量, 是否超过加载因子(长度 * 0.75), 进行扩容
        if (this.count > this.limit * 0.75) {
          var newSize = this.getPrime(this.limit * 2)
          this.resize(newSize)
        }
      }

      /* 在哈希表内寻找元素 */
      HashTable.prototype.get = function(key) {
        var index = this.hashFunc(key)
        var bucket = this.storage[index]
        if (!bucket) {
          return null //桶都不存在直接返回null
        }
        // 在桶内线性查找
        for (var i = 0, el; el = bucket[i++];) {
          if (el[0] === key) {
            return el[1]
          }
        }

        // 线性查找, 未查找到
        return null
      }

      HashTable.prototype.remove = function(key) {
        // 1. 找出元素下标
        var index = this.hashFunc(key)
        // 2. 取出下标对应的存储桶
        var bucket = this.storage[index]
        // 3. 如果没有桶, 返回删除失败
        if (!bucket) {
          return null
        }
        // 4. 桶中线性查找元素
        for (var i = 0, el; el = bucket[i++];) {
          if (el[0] === key) {
            var target = el[1] // 保存元素值
            bucket.splice(i - 1, 1) // 删除对应数组
            this.count -= 1 // 元素个数减少一

            /* 4-2: 减少元素后, 判断是否需要缩小容量 */
            if (this.count < this.limit * 0.25) {
              var newSize = this.getPrime(Math.floor(this.limit / 2))
              this.resize(newSize)
            }
            return target
          }
        }

        // 5. 有桶但桶中无元素
        return null
      }

      /* 哈希表中的长度 */
      HashTable.prototype.size = function() {
        return this.count
      }

      /* 哈希表元素是否为空 */
      HashTable.prototype.isEmpty = function() {
        return this.count === 0
      }

      /* 判断一个数是否为质数, 用于数组扩容 */
      HashTable.prototype.isPrime = function(num) {
        // 什么是质数: 大于等于2且小于自身的数里没有能被整除的数

        // 1. 循环次数较高
        // for(var i = 2; i < num; i++){
        //   if(num % i === 0) {
        //     return false
        //   }
        // }
        // return true

        // 2. 减少循环次数, 提升效率
        var pingFanGen = Math.ceil(Math.sqrt(num))
        for (var i = 2; i <= pingFanGen; i++) {
          if (num % i === 0) {
            return false
          }
        }
        return true
      }

      /* 数组扩容 */
      HashTable.prototype.getPrime = function(newSize) {
        while (!this.isPrime(newSize)) {
          newSize += 1
        }
        return newSize
      }

      /* 数组扩容 */
      HashTable.prototype.resize = function(newSize) {
        // 1. 保存旧的哈希表
        var oldStorage = this.storage
        // 2. 重置哈希表
        this.storage = []
        this.limit = newSize
        this.count = 0
        // 3. 拷贝旧哈希表
        for (var i = 0, bucket; bucket = oldStorage[i++];) {
          /* 3-1 如果旧存储桶不存在, 跳过此次循环 */
          if (!bucket) {
            continue
          }

          /* 3-2: 对每个存储桶的元素进行克隆 */
          for (var j = 0, el; el = bucket[j++];) {
            this.put(el[0], el[1])
          }
        }
      }
    }

    // var hash = new HashTable()
    // hash.put('no1','张飞')
    // hash.put('no2','赵云')
    // hash.put('n2o3','刘备')
    // hash.put('n22o1','关于')
    // hash.put('n2o1','张飞')
    // hash.put('n11o2','赵云')
    // hash.put('n222o3','刘备')
    // hash.put('no11111','关于')
    // hash.put('n2222222o1','张飞')
    // hash.put('n44o2','赵云')
    // hash.put('no553','刘备')
    // hash.put('no661','关于')
    // hash.put('no771','张飞')
    // hash.put('no882','赵云')
    // hash.put('no993','刘备')
    // hash.put('no001','关于')
    // // hash.remove('no1')
    // console.log(hash)

    /* ------------   二叉搜索树   -------------------------- */
    function BinarySearchTree() {
      // 内部类节点
      function Node(key) {
        this.left = null
        this.right = null
        this.key = key
      }
      this.root = null //根节点
      this.length = 0 // 当前二叉树节点的数量

      // 插入方法
      BinarySearchTree.prototype.insert = function(key) {
        // 1. 创建节点
        var node = new Node(key)
        // 2. 插入节点3
        // 2-1: 如果当前为空树
        if (this.root === null) {
          return this.root = node
        }
        // 2-2: 如果当前不为空树, 递归比较
        insertNode(this.root, node)
      }
      // 递归函数, 将当前节点和新节点依次对比
      function insertNode(currentNode, newNode) {
        // 1. 如果当前节点的key大于等于新节点的key, 插入右节点
        // 1-1: 如果当前节点的key的右节点为空, 直接插入
        // 1-2: 如果当前节点的右节点不为空, 递归比较右节点与新节点
        // 2. 如果当前节点的key小于新节点的key
        // 2-1: 如果当前节点的key的左节点为空, 直接插入
        // 1-2: 如果当前节点的左节点不为空, 递归比较左节点与新节点

        if (currentNode.key < newNode.key) {
          if (currentNode.right === null) {
            currentNode.right = newNode
          } else {
            insertNode(currentNode.right, newNode)
          }
        } else {
          if (currentNode.left === null) {
            currentNode.left = newNode
          } else {
            insertNode(currentNode.left, newNode)
          }
        }
      }

      // 先序遍历
      BinarySearchTree.prototype.preOrderTraversal = function(handler) {
        if (!this.root) return false // 如果还没有根节点, 返回false
        process(this.root, handler)

        // 1. 如果当前节点存在, 这是递归的结束条件
        // 2. 先序遍历, 先处理当前节点
        // 3. 再处理当前节点的左节点
        // 4. 最后处理当前节点的右节点
        function process(currentNode, handler) {
          if (currentNode) {
            handler(currentNode)
            process(currentNode.left, handler)
            process(currentNode.right, handler)
          }
        }
      }


      BinarySearchTree.prototype.midOrderTraversal = function(handler) {
        if (!this.root) return false // 1. 如果根节点不存在, 直接返回false

        process(this.root, handler)
        // 核心思路: 遇到左节点不处理, 直接继续遍历到底, 从最左侧叶子结点开始结束遍历, 处理程序
        function process(currentNode, handler) {
          if (!currentNode) return
          process(currentNode.left, handler)
          handler(currentNode)
          process(currentNode.right, handler)
        }
      }

      // 搜索二叉搜索树中的最大最小值
      // 1. 封装一个找到左节点的方法
      // 2. 递归调用该方法
      BinarySearchTree.prototype.min = function() {
        function getLeft(node) {
          // 如果当前节点不存在, 返回null, 没有左节点
          if (!node) return null
          var key = node.key
          if (node.left) {
            // 如果当前节点的左节点存在, 继续找
            key = getLeft(node.left)
          }
          return key
        }
        return getLeft(this.root)

      }
      // 搜索二叉搜索树中的最大最大值

      BinarySearchTree.prototype.max = function() {
        function getRight(node) {
          if (!node) return null
          var key = node.key
          if (node.right) {
            key = getRight(node.right)
          }
          return key
        }

        return getRight(node)
      }

      // 搜索二叉树搜索树中特点的值
      BinarySearchTree.prototype.get = function(key) {
        // 1. 情况一: root的值就是key
        // 2. root的值不是key
        //  2-1: 比当前节点大
        //    2-1-1: 向右查找
        //  2-2: 比当前节点小
        //    2-2-1: 向左查找
        //  2-3: 与当前节点相同, 结束节点查找

        function getTargetNode(currentNode, key) {
          if (!currentNode) return null
          // 向右查
          var isExist = false
          if (key > currentNode.key) {
            isExist = getTargetNode(currentNode.right, key)
          }
          else if (key < currentNode.key) {
            isExist = getTargetNode(currentNode.left, key)
          }
          else {
            isExist = true
          }
          return isExist
        }

        return getTargetNode(this.root, key)
      }

      // 删除二叉搜索树节点
      BinarySearchTree.prototype.remove = function (key) {
        // 1. 找到删除节点
        var currentNode = this.root, // 记录遍历的当前节点
          parent = null, // 记录父节点
          isLeftNode = true //记录当前节点是否为父节点的左子节点

        while (currentNode){
          parent = currentNode
          if(key < currentNode.key){
            isLeftNode = true
            currentNode = currentNode.left
          }else if(key > currentNode.key){
            isLeftNode = false
            currentNode = currentNode.right
          }else {
            break
          }
        }
        // 上边的循环在currentNode不存在和currentNode.key = key的情况下出来
        // 排除不存在的情况, 即剩下找到节点的情况.
        if(!currentNode){
          return false
        }

        // 情况一: 删除节点是叶子节点(既无左节点也无右节点, 不牵扯到子节点的位移)
        if(currentNode.left === null && currentNode.right === null){ //满足左右节点都是null的节点是叶节点
          // 如果是根节点, 如果是左节点, 如果是右节点三种情况讨论
          if(this.root === currentNode){
            return this.root = null
          }

          if(isLeftNode){
            return parent.left = null
          }

          if (!isLeftNode){
            return parent.right = null
          }
        }
        // 情况二:删除的节点只有一个子节点(就跟删除单向链表一样)
        if(currentNode.left === null){
          if(currentNode === this.root){
            return this.root = null
          }
          if(isLeftNode){
            return parent.left = currentNode.right
          }

          if(!isLeftNode){
            return parent.right = currentNode.right
          }
        }

        if(currentNode.right === null){
          if(currentNode === this.root){
            return this.root = null
          }
          if(isLeftNode){
            return parent.left = currentNode.left
          }
          if(!isLeftNode){
            return parent.right = currentNode.left
          }
        }
        // 情况三: 删除的节点有两个子节点
        var successor = this.getSuccessor(currentNode)
        if(isLeftNode){
          parent.left = successor
          successor.right = currentNode.right
        }else {
          parent.right = successor
        }

      }

      // 获取后继节点(后继节点: 右子树中最小的节点, 前驱节点: 左子树中最大的节点)
      BinarySearchTree.prototype.getSuccessor = function (delNode) {
        var successor = delNode.right,
          currentNode = delNode.right

        while (currentNode){
          successor = currentNode
          currentNode = currentNode.left
        }

        return successor
      }
    }

    var tree = new BinarySearchTree()
    tree.insert(1)
    tree.insert(2)
    tree.insert(3)
    console.log(tree)
    console.log(tree.remove(2))
  </script>
</body>

</html>